题目分析

又到了我们最害怕的hard数学题，数学题还是先找规律。直接在下面的题解中给出规律吧。

数学

本题考虑的子序列，而且只考虑序列的最小值和最大值，因此对于数组的顺序是无关的。这种问题可以首先进行排序。这是本题的关键，做和数组顺序无关的题，而且数据范围是满足排序的，往往都需要先进行排序。

排完序后发现以x为最大值的子序列个数就是x左边的所有元素选择或者不选择，以x为最小值的子序列个数就是x右边的所有元素选择或者不选择。

第一个元素n1，以n1为最大值的子序列只有1个，但是以n1为最小值的子序列有2的(len - 1)次方个。同理以第二个元素n2为最大值的子序列有n1可以选择或者不选择两个，以n2为最小值的子序列有2的(len - 2)次方个。

注意：从第一个元素开始，最大子序列个数逐渐 x 2，最小子序列个数逐渐 / 2，因为有求余的操作，因此可能会是奇数，所以当最小子序列个数为奇数个的时候，可以加上MOD，再除以2。

所以本题的解法很明确了，算法的时间复杂度为O(nlog(n))，空间复杂度为O(1)。

class Solution {
    private static final int MOD = 1000000007;

    public int sumSubseqWidths(int[] nums) {
        Arrays.sort(nums);
        long maxBit = 1;
        long minBit = pow(2, nums.length - 1);
        long res = 0;
        for (int x : nums) {
            res = (res + (maxBit - minBit) * x) % MOD;
            maxBit = (maxBit * 2) % MOD;
            minBit = ((minBit & 1) == 1 ? minBit + MOD : minBit) / 2;
        }
        return (int) res;
    }

    private long pow(int a, int b) {
        long res = 1;
        long cur = a;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = (res * cur) % MOD;
            }
            b >>= 1;
            cur = (cur * cur) % MOD;
        }
        return res;
    }
}

本题还可以继续优化，因为以第一个元素为最大值的子序列个数等于以最后一个元素为最小值的子序列个数，所以我们可以两边同时枚举，这样就不需要维护两个数量，一个 x 2，一个 / 2了。

虽然时间复杂度没有变化，但是代码更加优雅。

class Solution {
    private static final int MOD = 1000000007;

    public int sumSubseqWidths(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        long maxBit = 1;
        long res = 0;
        for (int i = 0; i < n; i++) {
            res = (res + (nums[i] - nums[n - 1 - i]) * maxBit) % MOD;
            maxBit = (maxBit * 2) % MOD;
        }
        return (int) res;
    }

    private long pow(int a, int b) {
        long res = 1;
        long cur = a;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = (res * cur) % MOD;
            }
            b >>= 1;
            cur = (cur * cur) % MOD;
        }
        return res;
    }
}

刷题总结

数学题一直是比较困难的，往往是找规律，贪心等方法，这些题目又是比较难想到的。对于这种题目，就是多见多做即可。